package binaryTree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTreeProblem {

    static class TreeNode{
        private int val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    /*
    * 226. 翻转二叉树
    * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
    */

    public TreeNode invertTree(TreeNode root) {
        //空树返回空
        if(root == null){
            return null;
        }
        //只有根结点，返回根结点
        if(root.left == null && root.right == null){
            return root;
        }
        //将左子树和右子树交换
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        //左子树继续交换
        invertTree(root.left);
        //右子树继续交换
        invertTree(root.right);
        //返回根结点
        return root;
    }

    /*
    * 100. 相同的树
    * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
    * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
    */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //都是空树，返回true
        if(p == null && q == null){
            return true;
        }
        //一棵是空树，一棵不是空树，返回false
        if(p == null || q == null){
            return false;
        }
        //根结点的值不相等，返回false
        if(p.val != q.val){
            return false;
        }
        //根结点的值相等，继续判断左右子树是否相同，左右子树均相同，返回true,否则返回false
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    /*
    * 101. 对称二叉树
    * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
    */
    public boolean isSymmetric(TreeNode root) {
        //空树是对称二叉树，返回true
        if(root == null){
            return true;
        }
        //非空树，检查左子树和右子树是否是对称二叉树，是返回true,否则返回false
        return isSameTree(root.left, root.right);
    }

//    public boolean isSameTree(TreeNode p, TreeNode q){
//        //均为空树，返回true
//        if(p == null && q == null){
//            return true;
//        }
//        //一棵空树，一棵非空，不是对称的返回false
//        if(p == null || q == null){
//            return false;
//        }
//        //均为非空树，他们的值不相等，不是对称的，返回false
//        if(p.val != q.val){
//            return false;
//        }
//        //左子树的左与右子树的右对称，左子树的右与右子树的左对称，是对称二叉树，返回true,否则返回false
//        return isSameTree(p.left, q.right) && isSameTree(p.right, q.left);
//    }


    /*
    *572. 另一棵树的子树
    * 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot
    * 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
    * 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
    */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //subRoot是空树，返回true
        if(subRoot == null){
            return true;
        }
        //subRoot是非空树，root是空树，返回false
        if(root == null){
            return false;
        }
        //判断两棵树是否相同的树
        boolean isSame = isSameTree(root, subRoot);
        //是则返回true
        if(isSame){
            return isSame;
        }
        //左右子树中只要存在相同的树，返回true,否则返回false
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

//    public boolean isSameTree(TreeNode p, TreeNode q) {
//        //都是空树，返回true
//        if(p == null && q == null){
//            return true;
//        }
//        //一棵是空树，一棵不是空树，返回false
//        if(p == null || q == null){
//            return false;
//        }
//        //根结点的值不相等，返回false
//        if(p.val != q.val){
//            return false;
//        }
//        //根结点的值相等，继续判断左右子树是否相同，左右子树均相同，返回true,否则返回false
//        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
//    }

    /*
    * 110. 平衡二叉树
    * 给定一个二叉树，判断它是否是 平衡二叉树
    */
    public boolean isBalanced(TreeNode root) {
        //空树是平衡二叉树，返回true
        if(root == null){
            return true;
        }
        //左右子树均为空树，则该树的是平衡二叉树，返回true
        if(root.left == null && root.right == null){
            return true;
        }
        //求左子树的高度
        int leftHeight = getHeight(root.left);
        //求右子树的高度
        int rightHeight = getHeight(root.right);
        //求左右子树高度差的绝对值，并判断其是否大于等于2，大于等于则不是平衡二叉树，返回true
        if(Math.abs(leftHeight - rightHeight) >= 2){
            return false;
        }
        //左右子树均为平衡二叉树，则该树是平衡二叉树，否则不是平衡二叉树
        return isBalanced(root.left) && isBalanced(root.right);
    }
    //求二叉树的高度
    public int getHeight(TreeNode root){
        //空树高度为0
        if(root == null){
            return 0;
        }
        //求左子树的高度
        int leftHeight = getHeight(root.left);
        //求右子树的高度
        int rightHeight = getHeight(root.right);
        //二叉树的高度 = 左右子树的最大高度 + 1
        return 1 + Math.max(leftHeight, rightHeight);

    }

    /*
    * 102. 二叉树的层序遍历
    * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）
    */
    public List<List<Integer>> levelOrder(TreeNode root) {
        //创建二维链表
        List<List<Integer>> llist = new ArrayList<>();
        //空树，返回llist
        if(root == null){
            return llist;
        }
        //创建一个链表
        List<Integer> list = new ArrayList<>();
        //创建两个队列
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();

        q1.offer(root);     //将根节点入队q1
        //遍历队列q1
        while(!q1.isEmpty()){
            //将队首出队，并将队首的值尾插入链表list
            TreeNode node = q1.poll();
            list.add(node.val);
            //左子树点非空入队q2
            if(node.left != null){
                q2.offer(node.left);
            }
            //右子树点非空入队q2
            if(node.right != null){
                q2.offer(node.right);
            }
            //q1为空，将q2赋给q1，将list尾插到llist中，list 指向新对象，q2指向新的对象
            if(q1.isEmpty()){
                q1 = q2;
                llist.add(list);
                list = new ArrayList<>();
                q2 = new LinkedList<>();
            }
        }

        return llist;
    }

    public static void main(String[] args) {
        System.out.println();
    }
}
